package Exercise;


import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.*;

import static java.math.BigDecimal.ROUND_UNNECESSARY;


public class AiExercise {

    //力扣300 最长子序列 动态规划
//    public static int lengthOfLIS(int[] nums) {
//        int []dp=new int[nums.length];
//        int n=nums.length;
//        int max=0;
//        for(int i=0;i<n;i++){
//            dp[i]=1;
//            for(int j=0;j<i;j++){
//                if(nums[j]<nums[i]){
//                    dp[i]=Math.max(dp[i],dp[j]+1);
//                }
//            }
//            max=Math.max(max,dp[i]);
//        }
//        return max;
//    }
//
//    public static void main(String[] args) {
//        int []a={10,9,2,5,3,7,101,18};
//        int result=lengthOfLIS(a);
//        System.out.println(result);
//
//    }


    //简单四则运算
//    public static int solution1(String expression) {
//        // Please write your code here
//        Stack<Integer> num = new Stack<>();
//        Stack<Character> ope = new Stack<>();
//
//        Map<Character,Integer> precedence=new HashMap<>();
//        precedence.put('+', 1);
//        precedence.put('-', 1);
//        precedence.put('*', 2);
//        precedence.put('/', 2);
//
//        int n=expression.length();
//        for (int i = 0; i < n; i++) {
//            int Sum=0;
//            char ch=expression.charAt(i);
//            if(ch >= '0' && ch <= '9') {
//                int tmpI=i;
//                while (ch >= '0' && ch <= '9') {
//                    int tmp = expression.charAt(tmpI) - '0';
//                    Sum = Sum * 10 + tmp;
//                    tmpI++;
//                    if(tmpI<n) {
//                        ch = expression.charAt(tmpI);
//                    }else{
//                        break;
//                    }
//                }
//                num.push(Sum);
//            }
//            else if(ch=='('){
//                ope.push(expression.charAt(i));
//            }
//            else if(ch==')') {
//                while(!ope.isEmpty()&&ope.peek()!='('){
//                    performOperation(num,ope);
//                }
//                ope.pop();
//            }
//            else if(precedence.containsKey(ch)){
//                while(!ope.isEmpty()&&ope.peek() != '(' &&precedence.get(ope.peek())>=precedence.get(ch)){
//                    performOperation(num,ope);
//                }
//                ope.push(ch);
//            }
//
//        }
//        while(!ope.isEmpty()){
//            performOperation(num,ope);
//
//        }
//        return num.pop();
//    }
//
//    public static int solution(String expression) {
//        // 初始化操作数栈和运算符栈
//        Stack<Integer> numStack = new Stack<>();
//        Stack<Character> opStack = new Stack<>();
//
//        // 定义运算符优先级
//        Map<Character, Integer> precedence = new HashMap<>();
//        precedence.put('+', 1);
//        precedence.put('-', 1);
//        precedence.put('*', 2);
//        precedence.put('/', 2);
//
//        // 遍历表达式
//        for (int i = 0; i < expression.length(); i++) {
//            char ch = expression.charAt(i);
//
//            if (Character.isDigit(ch)) {
//                int num = ch - '0';
//                while (i + 1 < expression.length() && Character.isDigit(expression.charAt(i + 1))) {
//                    num = num * 10 + (expression.charAt(++i) - '0');
//                }
//                numStack.push(num);
//            } else if (ch == '(') {
//                opStack.push(ch);
//            } else if (ch == ')') {
//                while (!opStack.isEmpty() && opStack.peek() != '(') {
//                    performOperation(numStack, opStack);
//                }
//                opStack.pop(); // 弹出左括号
//            } else if (precedence.containsKey(ch)) {
//                while (!opStack.isEmpty() &&opStack.peek() != '(' && precedence.get(opStack.peek()) >= precedence.get(ch)) {
//                    performOperation(numStack, opStack);
//                }
//                opStack.push(ch);
//            }
//        }
//
//        // 处理剩余的运算符
//        while (!opStack.isEmpty()) {
//            performOperation(numStack, opStack);
//        }
//
//        // 返回最终结果
//        return numStack.pop();
//    }
//
//    private static void performOperation(Stack<Integer> numStack, Stack<Character> opStack) {
//        int b = numStack.pop();
//        int a = numStack.pop();
//        char op = opStack.pop();
//        switch (op) {
//            case '+':
//                numStack.push(a + b);
//                break;
//            case '-':
//                numStack.push(a - b);
//                break;
//            case '*':
//                numStack.push(a * b);
//                break;
//            case '/':
//                numStack.push(a / b); // 注意：这里只保留整数结果
//                break;
//        }
//    }
//    public static void main(String[] args) {
//        // You can add more test cases here
//        System.out.println(solution1("1+1") == 2);
//        System.out.println(solution1("3+4*5/(3+2)") == 7);
//        System.out.println(solution1("4+2*5-2/1") == 12);
//        System.out.println(solution1("(1+(4+5+2)-3)+(6+8)") == 23);
//        System.out.println(solution1("8-3+(6*4)/3")==13);
//    }


//    选择题反选效果分析
//    public static String solution(int n, String s, String t) {
//        // write code here
//        int count1=0;
//        int count2=0;
//        char [] tmp=new char[s.length()];
//        for (int i = 0; i < s.length(); i++) {
//            if(s.charAt(i)==t.charAt(i)){
//                count1++;
//            }
//            if(s.charAt(i)=='A'){
//                if(t.charAt(i)=='B')
//                    count2++;
//            }else{
//                if(t.charAt(i)=='A')
//                    count2++;
//            }
//        }
//        if(count1<count2)
//            return "yes";
//        else if(count1==count2)
//            return "draw";
//        else
//            return "no";
//    }
//    public static void main(String[] args) {
//        System.out.println(solution(2, "AB", "AA").equals("draw"));
//        System.out.println(solution(3, "BAA", "ABB").equals("yes"));
//        System.out.println(solution(4, "ABAB", "BABA").equals("yes"));
//    }


    //红包运气排行榜
//    public static List<String> solution(int n, List<String> s, List<Integer> x) {
//        // write code here
//        // 创建一个数据结构来存储每个人的信息
//        List<Person> people = new ArrayList<>();
//        // 创建一个Map用来表示每个人信息
//        Map<String, Person> map = new HashMap<>();
//        for (int i = 0; i < n; i++) {
//
//        }
//        // 填充数据
//        for (int i = 0; i < n; i++) {
//            // 如果map里的key没有，我们直接创建Perosn，然后向map里面添加数据即可
//            if (!map.containsKey(s.get(i))) {
//                map.put(s.get(i), new Person(s.get(i), x.get(i), i));
//                people.add(new Person(s.get(i), x.get(i), i));
//            } else {
//                // 如果map里key已经有了，那么我们就将他的金额相加即可
//                Person person = map.get(s.get(i));
//                person.setAmount(person.getAmount() + x.get(i));
//            }
//        }
//        // 我们只需要map的value来排序即可
//        List<Person> values = new ArrayList<>(map.values());
//        // 提取结果
//        Collections.sort(values, new Comparator<Person>() {
//            @Override
//            public int compare(Person o1, Person o2) {
//                // 如果金额不同，那我们就按金额大小逆序
//                if (o1.amount != o2.getAmount()) {
//                    return o2.amount - o1.amount;
//                }
//                // 如果金额相同，那么我们就按索引升序
//                return o1.index - o2.index;
//            }
//        });
//        List<String> result = new ArrayList<>();
//        // 遍历value，此时的value已经按照我们预想的排序排好了
//        for (Person person : values) {
//            // 按照题目要求，取出person里的name字段
//            result.add(person.name);
//        }
//        System.out.println(result);
//        return result;
//    }
//
//    // 定义一个类来存储每个人的信息
//    static class Person {
//        String name;
//        int amount;
//        int index;
//
//        public Person(String name, int amount, int index) {
//            this.name = name;
//            this.amount = amount;
//            this.index = index;
//        }
//
//        public void setAmount(int amount) {
//            this.amount = amount;
//        }
//
//        public int getAmount() {
//            return this.amount;
//        }
//
//    }
//
//    public static void main(String[] args) {
//        System.out.println(solution(4, Arrays.asList("a", "b", "c", "d"), Arrays.asList(1, 2, 2, 1)).equals(Arrays.asList("b", "c", "a", "d")));
//        System.out.println(solution(3, Arrays.asList("x", "y", "z"), Arrays.asList(100, 200, 200)).equals(Arrays.asList("y", "z", "x")));
//        System.out.println(solution(5, Arrays.asList("m", "n", "o", "p", "q"), Arrays.asList(50, 50, 30, 30, 20)).equals(Arrays.asList("m", "n", "o", "p", "q")));
//        System.out.println(solution(12,Arrays.asList("aa","aaaaaaa","aaaa","aaaa","aaaa","aaaaaaaaaa","aaaaaaaaa","aaaa","aaaaaaaaaa","aaaaaaaaa","aaaaa","aaaa"),
//                Arrays.asList(17,14,11,2,8,16,14,17,10,6,5,12)).equals(Arrays.asList("aaaa","aaaaaaaaaa","aaaaaaaaa","aa","aaaaaaa","aaaaa")));


//    组成字符串ku的最大次数
//        public static int solution(String s) {
//            // write code here
//            int count1=0;
//            int count2=0;
//            for (int i = 0; i < s.length(); i++) {
//                if(s.charAt(i)=='k'||s.charAt(i)=='K'){
//                    count1++;
//                }
//                if(s.charAt(i)=='u'||s.charAt(i)=='U'){
//                    count2++;
//                }
//            }
//            return count1>count2?count2:count1;
//        }
//        public static void main(String[] args) {
//            System.out.println(solution("AUBTMKAxfuu") == 1);
//            System.out.println(solution("KKuuUuUuKKKKkkkkKK") == 6);
//            System.out.println(solution("abcdefgh") == 0);
//        }


    //游戏英雄升级潜力评估  困笑
//    public static int solution(int n, int[] u) {
//        // write code here
//        int min=Integer.MAX_VALUE;
//        for(int i=0;i<n;i++){
//            if(u[i]<min){
//                min=u[i];
//            }
//        }
//        int count=0;
//        for(int i=0;i<n;i++){
//            if(u[i]>min){
//                count++;
//            }
//        }
//        return count;
//    }
//
//    public static void main(String[] args) {
//        System.out.println(solution(5, new int[]{1, 2, 3, 1, 2}) == 3);
//        System.out.println(solution(4, new int[]{100000, 100000, 100000, 100000}) == 0);
//        System.out.println(solution(6, new int[]{1, 1, 1, 2, 2, 2}) == 3);
//    }


    //小E的怪物挑战
//    public static int solution(int n, int H, int A, int[] h, int[] a) {
//        // write code here
//        int[] dp = new int[n];
//        int max = 0;
//        for (int i = 0; i < n; i++) {
//            if (h[i] > H || a[i] > A) {
//                continue;
//            }
//            dp[i] = 1;
//            for (int j = 0; j < i; j++) {
//                if (h[i] > h[j] && a[i] > a[j]) {
//                    dp[i] = Math.max(dp[i], dp[j] + 1);
//                }
//            }
//            max = Math.max(max, dp[i]);
//        }
//        return max;
//    }
//
//    public static void main(String[] args) {
//        System.out.println(solution(3, 4, 5, new int[]{1, 2, 3}, new int[]{3, 2, 1}) == 1);
//        System.out.println(solution(5, 10, 10, new int[]{6, 9, 12, 4, 7}, new int[]{8, 9, 10, 2, 5}) == 2);
//        System.out.println(solution(4, 20, 25, new int[]{10, 15, 18, 22}, new int[]{12, 18, 20, 26}) == 3);
//    }


    //小U的问号替换问题
//    public static int solution(String s, int p) {
////        int mod = 1000000007;
////        int n = s.length();
////        int[][] dp = new int[n + 1][p];
////
////        // 初始状态
////        dp[0][0] = 1;
////
////        // 遍历字符串的每一位
////        for (int i = 1; i <= n; i++) {
////            char c = s.charAt(i - 1);
////            for (int r = 0; r < p; r++) {
////                if (c == '?') {
////                    // 尝试所有可能的数字
////                    for (int digit = 0; digit <= 9; digit++) {
////                        int newR = (r * 10 + digit) % p;
////                        dp[i][newR] = (dp[i][newR] + dp[i - 1][r]) % mod;
////                    }
////                } else {
////                    // 直接更新余数
////                    int digit = c - '0';
////                    int newR = (r * 10 + digit) % p;
////                    dp[i][newR] = (dp[i][newR] + dp[i - 1][r]) % mod;
////                }
////            }
////        }
////
////        // 最终结果
////        return dp[n][0];
//
//        int mod=1000000007;
//        int n=s.length();
//        //其中数组的行数表示是第几个字符，列数表示余数
//        //一共有n个字符 0个字符的也算是一种 所以应该有n+1个字符 那么定义数组的时候就要定义n+1个
//        //余数是0-（p-1），定义列数为p即可
//        int [][]dp=new int[n+1][p];
//        //初始条件
//        //长度为0的时候 （空字符串）  余数为0的情况有一种
//        dp[0][0]=1;
//        //遍历字符的每一位
//        //从1开始 字符串长度为0 只有余数为0这一种情况 已经定义
//        for(int i=1;i<=n;i++){
//            //表示第几个字符（索引比第几个小1）
//            char c=s.charAt(i-1);
//            //r表示上一位的余数
//            for(int r=0;r<p;r++) {
//                //如果是? 那么尝试所有余数的可能性
//                if (c == '?') {
//                    for (int j = 0; j <= 9; j++) {
//                        int newJ = (r * 10 +j)%p;
//                        dp[i][newJ]=(dp[i-1][r]+dp[i][newJ])%mod;
//                    }
//                }
//                //直接更新余数
//                else{
//                    int j=c-'0';
//                    int newJ=(r*10+j)%p;
//                    dp[i][newJ]=(dp[i-1][r]+dp[i][newJ])%mod;
//                }
//            }
//        }
//        return dp[n][0];
//    }
//
//    public static void main(String[] args) {
//        System.out.println(solution("??", 1) == 100);
//        System.out.println(solution("????1", 12) == 0);
//        System.out.println(solution("1??2", 3) == 34);
//    }


    //a替换函数
//    public static String solution(String s) {
//        // write code here
//        StringBuilder sb=new StringBuilder();
//        for(int i=0;i<s.length();i++){
//            char c=s.charAt(i);
//            if(c=='a'){
//                sb.append("%100");
//            }else{
//                sb.append(c);
//            }
//        }
//        return sb.toString();
//    }
//
//    public static void main(String[] args) {
//        System.out.println(solution("abcdwa").equals("%100bcdw%100"));
//        System.out.println(solution("banana").equals("b%100n%100n%100"));
//        System.out.println(solution("apple").equals("%100pple"));
//    }


    //第三大分数
//    public static int solution(int n, int[] nums) {
//        // write code here
//        if(n==1){
//            return nums[0];
//        }
//        if(n==2){
//            return Math.max(nums[0],nums[1]);
//        }
//
//        int first=0;
//        int second=0;
//        int third=0;
//        for(int i=0;i<n-1;i++){
//            for(int j=0;j<n-i-1;j++){
//                if(nums[j]>nums[j+1]){
//                    int tmp=nums[j];
//                    nums[j]=nums[j+1];
//                    nums[j+1]=tmp;
//                }
//            }
//
//        }
//        int count1=0;
//        int count2=0;
//        for(int i=n-1; i>=0;i--){
//            if(nums[i]>=first){
//                first=nums[i];
//                count1++;
//            }else if(nums[i]>=second){
//                second=nums[i];
//                count2++;
//            }else if(nums[i]>third&&nums[i]!=second){
//                third=nums[i];
//            }
//        }
//        if(count1+count2==n){
//            return first;
//        }
//        return third;
//
//    }
//    public static void main(String[] args) {
//        System.out.println(solution(3, new int[]{3, 2, 1}) == 1);
//        System.out.println(solution(2, new int[]{1, 2}) == 2);
//        System.out.println(solution(4, new int[]{2, 2, 3, 1}) == 1);
//        System.out.println(solution(12, new int[]{2,8,13,9,7,6,7,4,1,4,10,12}) == 10);
//        System.out.println(solution(3,new int[]{15,12,15})==15);
//    }
    //最少步数归零问题  （难度困难） 搞笑
//    public static int solution(int n, int[] a) {
//        // write code here
//        int count=0;
//
//        for(int i=0;i<n;i++){
//            while(a[i]!=0){
//                if(a[i]%10!=0){
//                    count++;
//                }
//                a[i]/=10;
//            }
//        }
//
//        return count;
//    }
//
//    public static void main(String[] args) {
//        System.out.println(solution(5, new int[]{10, 13, 22, 100, 30}) == 7);
//        System.out.println(solution(3, new int[]{5, 50, 505}) == 4);
//        System.out.println(solution(4, new int[]{1000, 1, 10, 100}) == 4);
//    }


    //点菜
//    public static long solution(int m, int[] w) {
//        // write code here
//        int max=0;
//        for(int i=0;i<w.length;i++){
//            int count=0;
//            for(int j=i;j<w.length;j++){
//                if(w[i]==w[j]&&w[i]<=m){
//                    count++;
//                }
//            }
//            if(count>=max){
//                max=count;
//            }
//        }
//        return max;
//    }
//
//    public static void main(String[] args) {
//        System.out.println(solution(6, new int[]{2, 3, 3, 6, 6, 6, 9, 9, 23}) == 3);
//        System.out.println(solution(4, new int[]{1, 2, 4, 4, 4}) == 3);
//        System.out.println(solution(5, new int[]{5, 5, 5, 5, 6, 7, 8}) == 4);
//    }


//    小U的数字插入问题 字符串简单 数组纯构式
//    public static int solution(int a, int b) {
//    // write code here
//        String strA = String.valueOf(a);
//        String strB = String.valueOf(b);
//
//        // Initialize the result with the smallest possible value
//        String maxResult = strA + strB;
//
//        // Try inserting b at every possible position in a
//        for (int i = 0; i <= strA.length(); i++) {
//            String candidate = strA.substring(0, i) + strB + strA.substring(i);
//            if (candidate.compareTo(maxResult) > 0) {
//                maxResult = candidate;
//            }
//        }
//
//        // Convert the result back to an integer
//        return Integer.parseInt(maxResult);
//    }
//
//    public static void main(String[] args) {
//        System.out.println(solution(76543, 4) == 765443);
//        System.out.println(solution(1, 0) == 10);
//        System.out.println(solution(44, 5) == 544);
//        System.out.println(solution(666, 6) == 6666);
//    }


    //兔群
//    public static long solution(int A) {
//        // Edit your code here
//        long a = 1;
//        long b = 1;
//        long c = 1;
//        A+=1;
//        while (A >= 3) {
//            c = a + b;
//            a = b;
//            b = c;
//            A--;
//        }
//        return c;
//    }
////
//    public static void main(String[] args) {
//        // Add your test cases here
//        System.out.println(solution(1) == 1L);
//        System.out.println(solution(5) == 8L);
//        System.out.println(solution(15) == 987L);
//        System.out.println(solution(50) == 20365011074L);
//    }


    //概率问题
//    public static int solution(int n, int k) {
    // write code here
//        long molecule=k-1;
//        long denominator=k+1;
//
//        long sum1=1;
//        long sum2=1;
//        while(n!=0){
//            long i=1;
//            sum1*=molecule;
//            sum2*=denominator;
//            long a=sum1;
//            long b=sum2;
//            while(i!=0){
//                i=a%b;
//                a=b;
//                b=i;
//            }
//            sum1/=a;
//            sum2/=a;
//            n--;
//        }
//        molecule=sum1;
//        denominator=sum2;
//        if(molecule%2==0){
//            molecule/=2;
//        }else{
//            denominator*=2;
//        }
//        if(denominator%2==0){
//            molecule+=(denominator/2);
//        }else{
//            molecule=molecule*2+denominator;
//            denominator*=2;
//        }
//        if(molecule==denominator){
//            return 1;
//        }else{
//            long i=1;
//            long a=molecule;
//            long b=denominator;
//            while(i!=0){
//                i=a%b;
//                a=b;
//                b=i;
//            }
//            molecule/=a;
//            denominator/=a;
//            return (int)(molecule+denominator)%10;
//        }
//        BigInteger molecule = BigInteger.valueOf(k - 1);
//        BigInteger denominator = BigInteger.valueOf(k + 1);
//
//        BigInteger numeratorProduct = BigInteger.ONE;
//        BigInteger denominatorProduct = BigInteger.ONE;
//
//        while (n != 0) {
//            numeratorProduct = numeratorProduct.multiply(molecule);
//            denominatorProduct = denominatorProduct.multiply(denominator);
//
//            // 计算最大公约数并化简
//            BigInteger gcd = numeratorProduct.gcd(denominatorProduct);
//            numeratorProduct = numeratorProduct.divide(gcd);
//            denominatorProduct = denominatorProduct.divide(gcd);
//
//            n--;
//        }
//        // 处理分数的化简
//        if (numeratorProduct.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
//            numeratorProduct = numeratorProduct.divide(BigInteger.valueOf(2));
//        } else {
//            denominatorProduct = denominatorProduct.multiply(BigInteger.valueOf(2));
//        }
//        if (denominatorProduct.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
//            numeratorProduct = numeratorProduct.add(denominatorProduct.divide(BigInteger.valueOf(2)));
//        } else {
//            numeratorProduct = numeratorProduct.multiply(BigInteger.valueOf(2)).add(denominatorProduct);
//            denominatorProduct = denominatorProduct.multiply(BigInteger.valueOf(2));
//        }
//        if (numeratorProduct.equals(denominatorProduct)) {
//            return 1;
//        } else {
//            BigInteger gcd = numeratorProduct.gcd(denominatorProduct);
//            numeratorProduct = numeratorProduct.divide(gcd);
//            denominatorProduct = denominatorProduct.divide(gcd);
//            return (numeratorProduct.add(denominatorProduct)).mod(BigInteger.TEN).intValue();
//        }
//    }
//
//    public static void main(String[] args) {
//        System.out.println(solution(2, 5) == 1);
//        System.out.println(solution(2, 6) == 6);
//        System.out.println(solution(3, 7) == 9);
//        System.out.println(solution(3, 9) == 9);
//        System.out.println(solution(13, 17) == 5);
//    }


    //字符串最短循环字串
//    public static String solution(String inp) {
////     Edit your code here
//        int i=0;
//        int j=1;
//        while(j<inp.length()){
//            int length=j-i;
//            int tmp=j;
//            while(tmp<inp.length()&&tmp+length<=inp.length()&&inp.substring(i,tmp).equals(inp.substring(tmp,tmp+length))){
//                i+=length;
//                tmp+=length;
//                if(tmp==inp.length()){
//                    return inp.substring(0,j);
//                }
//            }
//            i=0;
//            j++;
//        }
//        return "";
//    }
//
//    //
//    public static void main(String[] args) {
//        // Add your test cases here
//        System.out.println(solution("abcabcabcabc").equals("abc"));
//        System.out.println(solution("aaa").equals("a"));
//        System.out.println(solution("abababab").equals("ab"));
//        System.out.println(solution("abcdabcdabcdabcd").equals("abcd"));
//        System.out.println(solution("b").equals(""));
//        System.out.println(solution("abcabcdaalval").equals(""));
//        System.out.println(solution("aabccbcbbbcccaccca").equals(""));
//        System.out.println(solution("aaabab").equals(""));
//    }


    //奇妙货币
//    public static String solution(int V, int W) {
//        // Edit your code here
//
//
//        return "NO";
//    }
//
//    public static void main(String[] args) {
//        // Add your test cases here
//        System.out.println(solution(10, 9) == "YES");
//        System.out.println(solution(200, 40199) == "YES");
//        System.out.println(solution(108, 50) == "NO");
//
//    }


    //迷人子序列
//    public static int solution(int n, int k, List<Integer> sequence) {
////             Please write your code here
//        int left = 0;
//        int right = 0;
//        int count = 0;
//
//        return -1;
//    }
//
//
//    public static void main(String[] args) {
//
//        // You can add more test cases here
//        List<Integer> sequence1 = new ArrayList<>();
//        sequence1.add(3);
//        sequence1.add(1);
//        sequence1.add(2);
//        sequence1.add(4);
//
//        List<Integer> sequence2 = new ArrayList<>();
//        sequence2.add(0);
//        sequence2.add(3);
//        sequence2.add(4);
//        sequence2.add(5);
//        sequence2.add(2);
//        sequence2.add(1);
//        sequence2.add(6);
//        sequence2.add(7);
//        sequence2.add(8);
//        sequence2.add(9);
//
//        List<Integer> sequence3 = new ArrayList<>();
//        sequence3.add(1);
//        sequence3.add(3);
//        sequence3.add(5);
//        sequence3.add(5);
//        sequence3.add(3);
//        sequence3.add(1);
//
//        System.out.println(solution(4, 2, sequence1) == 5);
//        System.out.println(solution(10, 5, sequence2) == 28);
//        System.out.println(solution(6, 3, sequence3) == 14);
//    }


//    最大回文子串 中心扩散法 偷
//    public static String longestPalindrome(String s) {
//        int len=1;
//        int left=0;
//        int right=0;
//        int maxLen=0;
//        int maxStart=0;
//        int length=s.length();
//
//        for(int i=0;i<length;i++){
//            left=i-1;
//            right=i+1;
//            while(left>=0&&s.charAt(i)==s.charAt(left)){
//                left--;
//                len++;
//            }
//            while(right<length&&s.charAt(i)==s.charAt(right)){
//                right++;
//                len++;
//            }
//            while(right<length&&left>=0&&s.charAt(left)==s.charAt(right)){
//                right++;
//                left--;
//                len++;
//            }
//            if(len>maxLen){
//                maxLen=len;
//                maxStart=left;
//            }
//            len=1;
//
//        }
//        return s.substring(maxStart+1,maxStart+maxLen+1);
//    }
//    public static void main(String[] args) {
//        long start=System.currentTimeMillis();
//        String s="eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee";
//        String s1 = longestPalindrome(s);
//        long end=System.currentTimeMillis();
//        System.out.println(s1);
//        System.out.println(end-start);
//
//    }


    //超时 最大回文子串
//    public static String longestPalindrome(String s) {
//        String finalStr="";
//        if(s.length()==1){
//            return s;
//        }
//
//        for(int i=0;i<s.length();i++){
//            for(int j=s.length()-1;j>=i;j--) {
//                int tmp1=i;
//                int tmp2=j;
//                StringBuilder sb = new StringBuilder();
//                while (s.charAt(tmp1) == s.charAt(tmp2) && tmp1 < tmp2) {
//                    tmp1++;
//                    tmp2--;
//                }
//                if (tmp1 >= tmp2) {
//                    for (int a = i; a <= j; a++) {
//                        sb.append(s.charAt(a));
//                    }
//                    if (finalStr.length() <sb.toString().length() ) {
//                        finalStr = sb.toString();
//                    }
//                }
//            }
//
//
//        }if(finalStr.equals("")){
//            StringBuilder sb=new StringBuilder();
//            sb.append(s.charAt(0));
//            return sb.toString();
//        }else {
//            return finalStr;
//        }
//    }

    //KMP算法
//    public static ArrayList<Integer> findSubsequenceOccurrences(String dna, String target) {
//        ArrayList<Integer> Index = new ArrayList<>();
//        int i = 0;
//        int[] Next = next(target);
//        int j = 0;
//        while (i < dna.length()) {
//            if (j != 0) {
//                i -= (Next[target.length() - 1] + 2);
//                j = 0;
//            }
//            while (i < dna.length() && j < target.length()) {
//                if (j == -1 || dna.charAt(i) == target.charAt(j)) {
//                    ++i;
//                    ++j;
//                } else {
//                    j = Next[j];
//                }
//            }
//            if (j > target.length() - 1) {
//                Index.add(i - target.length());
//            }
//        }
//
//        return Index;
//    }
//
//    public static int[] next(String s) {
//        int i = 0;
//        int j = -1;
//        int[] nextArr = new int[s.length()];
//        nextArr[0] = -1;
//        while (i < s.length() -1) {
//            if (j == -1 || s.charAt(i) == s.charAt(j)) {
//                ++i;
//                ++j;
//                nextArr[i] = j;
//            } else {
//                j = nextArr[j];
//            }
//        }
//        return nextArr;
//    }
//
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        System.out.println("输入DNA字符序列");
//        String s1 = sc.nextLine();
//        System.out.println("输入目标子序列");
//        String s2 = sc.nextLine();
//        ArrayList<Integer> integers = findSubsequenceOccurrences(s1, s2);
//        System.out.println(integers);
//    }


    //外卖超时 未完成
//    public static String solution(String t1, String t2, String t3) {
//        // write code here
//        for (int i = 0; i < t1.length(); i++) {
//            if(t2.charAt(0)=='0'&&t2.charAt(1)=='0'){
//                if(t3.charAt(0)=='2'&&t3.charAt(1)=='3'){
//                    return "No";
//                }
//            }
//            if(t3.charAt(i)-'0'>t2.charAt(i)-'0'){
//
//            }
//        }
//
//        return "";
//    }
//
//    public static void main(String[] args) {
//        System.out.println(solution("18:00", "19:05", "19:05").equals("No"));
//        System.out.println(solution("23:00", "00:21", "00:23").equals("Yes"));
//        System.out.println(solution("23:05", "00:05", "23:58").equals("No"));
//    }


    //射击靶子
//    public static int solution(int x, int y) {
//        // write code here
//        for(int i=1;i<=10;i++){
//            if(x*x+y*y<=i*i){
//                return 11-i;
//            }
//        }
//        return 0;
//    }
//
//    public static void main(String[] args) {
//        System.out.println(solution(1, 0) == 10);
//        System.out.println(solution(1, 1) == 9);
//        System.out.println(solution(0, 5) == 6);
//        System.out.println(solution(3, 4) == 6);
//    }


    //版本号比较
//    public static void main(String[] args) {
//        System.out.println(solution("0.1", "1.1") == -1);
//        System.out.println(solution("1.0.1", "1") == 1);
//        System.out.println(solution("7.5.2.4", "7.5.3") == -1);
//        System.out.println(solution("1.0", "1.0.0") == 0);
//    }
//
//    public static int solution(String version1, String version2) {
//        // Edit your code here
//        int count = 0;
//        int length = version1.length() <= version2.length() ? version1.length() : version2.length();
//        int length1 = version1.length() >= version2.length() ? version1.length() : version2.length();
//        for (int i = 0; i < length; i++) {
//            if (version1.charAt(i) - '0' > version2.charAt(i) - '0') {
//                return 1;
//            } else if (version1.charAt(i) - '0' < version2.charAt(i) - '0') {
//                return -1;
//            } else {
//                count++;
//            }
//        }
//        if (count == length) {
//            int tmp = length1 - length;
//            if (version1.length() > version2.length()) {
//                while (tmp != 0) {
//                    if(version1.charAt(version1.length()-tmp)!='.'&&version1.charAt(version1.length()-tmp)!='0'){
//                        return 1;
//                    }
//                    tmp--;
//                }
//            } else {
//                while (tmp != 0) {
//                    if(version2.charAt(version2.length()-tmp)!='.'&&version2.charAt(version2.length()-tmp)!='0'){
//                        return -1;
//                    }
//                    tmp--;
//                }
//            }
//        }
//        return 0;
//    }

    //完美数字
//    public static int solution(int x, int y) {
//        // Edit your code here
//        int count = 0;
//        int count1 = 0;
//        for (int i = x; i <= y; i++) {
//            if (i / 10 == 0) {
//                count++;
//                continue;
//            }
//            int a = i;
//            int i1 = a % 10;
//            a /= 10;
//            while (a != 0) {
//                if (i1 == a % 10) {
//                    a /= 10;
//                } else {
//                    break;
//                }
//            }
//            if (a == 0) {
//                count++;
//            }
//        }
//        return count;
//    }
//
//    public static void main(String[] args) {
//        // Add your test cases here
//
//        System.out.println(solution(1, 10) == 9);
//        System.out.println(solution(2, 22) == 10);
//    }


    //葫芦 两个小时debug
//    public static int[] solution(int n, int max, int[] array) {
//        // Edit your code here
//        int[] countMap = new int[14];
//        for (int i = 0; i < array.length; i++) {
//            countMap[array[i]] += 1;
//        }
//        int a[] = new int[14];
//        for (int i = 0; i < countMap.length; i++) {
//            if (countMap[i] >= 2) {
//                a[i] = i;
//            }
//        }
//        int[] finalInt = new int[2];
//        int maxA = 0;
//        int maxB = 0;
//        for (int i = 0; i < a.length; i++) {
//            if (countMap[i] >= 3) {
//                if (a[i] == 1) {
//                    maxA = 1;
//                } else if (a[i] > maxA && maxA != 1) {
//                    maxA = a[i];
//                }
//                for (int i1 = 0; i1 < a.length; i1++) {
//                    if (countMap[i1] >= 3 && a[i] != a[i1]) {
//                        int tmp1 = a[i] > a[i1] ? a[i] : a[i1];
//                        int tmp2 = a[i] > a[i1] ? a[i1] : a[i];
//                        int tmp = tmp1 * 3 + tmp2 * 2;
//                        if (tmp > max) {
//                            int tmpTrue = tmp2 * 3 + tmp1 * 2;
//                            if (tmpTrue <= max) {
//                                if ((a[i1]>=finalInt[1]&&tmp2>=finalInt[0])||finalInt[0]==0) {
//                                    if(finalInt[0] != 1){
//                                    finalInt[0] = a[i];}
//                                    if((a[i1]>=finalInt[1]&&finalInt[1] != 1&&finalInt[0]!=a[i1])||finalInt[1]==0||finalInt[1]==finalInt[0]||finalInt[0]*3+finalInt[1]*2>max) {
//                                        finalInt[1] = a[i1];
//                                    }
//                                }
//                            }
//                        }
//                        if (tmp <= max) {
//                            if (tmp1 >= maxA) {
//                                if(finalInt[0] != 1){
//                                    finalInt[0] = a[i];}
//                                if((a[i1]>=finalInt[1]&&finalInt[1] != 1&&finalInt[0]!=a[i1])||finalInt[1]==0||finalInt[1]==finalInt[0]||finalInt[0]*3+finalInt[1]*2>max) {
//                                    finalInt[1] = a[i1];
//                                }
//                            }
//                        }
//                    } else if (countMap[i1] == 2) {
//                        if (a[i] * 3 + a[i1] * 2 <= max) {
//                            if (a[i] >= maxA) {
//                                if(finalInt[0] != 1){
//                                    finalInt[0] = a[i];}
//                                if((a[i1]>=finalInt[1]&&finalInt[1] != 1&&finalInt[0]!=a[i1])||finalInt[1]==0||finalInt[1]==finalInt[0]||finalInt[0]*3+finalInt[1]*2>max) {
//                                    finalInt[1] = a[i1];
//                                }
//                            }
//                        }
//                    }
//                }
//            }
//        }
//        if (finalInt[0] != 0) {
//            return finalInt;
//        }
//        return new int[]{0, 0};
//    }
//
//    public static void main(String[] args) {
//        // Add your test cases here
//
//        System.out.println(java.util.Arrays.equals(solution(9, 34, new int[]{6, 6, 6, 8, 8, 8, 5, 5, 1}), new int[]{8, 5}));
//        System.out.println(java.util.Arrays.equals(solution(9, 37, new int[]{9, 9, 9, 9, 6, 6, 6, 6, 13}), new int[]{6, 9}));
//        System.out.println(java.util.Arrays.equals(solution(9, 40, new int[]{1, 11, 13, 12, 7, 8, 11, 5, 6}), new int[]{0, 0}));
//        System.out.println(java.util.Arrays.equals(solution(31, 42, new int[]{3, 3, 11, 12, 12, 2, 13, 5, 13, 1, 13, 8, 8, 1, 8, 13, 12, 9, 2, 11, 3, 5, 8, 11, 1, 11, 1, 5, 4, 2, 5}), new int[]{1, 13}));
//        System.out.println(java.util.Arrays.equals(solution(28, 104, new int[]{2,6,12,2,8,12,12,7,10,4,11,8,6,2,3,12,9,8,6,6,3,10,10,9,3,10,2,8}), new int[]{12, 10}));
//        System.out.println(java.util.Arrays.equals(solution(31, 17, new int[]{11,10,8,1,2,9,13,1,10,6,8,2,9,7,2,9,8,10,9,3,7,13,7,1,1,5,12,10,12,2,5}), new int[]{1, 7}));
//        System.out.println(java.util.Arrays.equals(solution(44, 36, new int[]{10,11,6,13,9,7,6,2,2,2,4,10,4,3,3,7,2,4,5,11,12,10,7,9,5,13,8,1,6,9,3,8,10,11,5,3,7,11,1,8,4,5,9,6}), new int[]{11, 1}));
//        System.out.println(java.util.Arrays.equals(solution(26, 105, new int[]{7,4,8,2,4,11,4,13,9,2,11,13,5,11,2,7,8,11,10,2,7,8,7,13,13,12}), new int[]{13, 11}));
//        System.out.println(java.util.Arrays.equals(solution(30, 38, new int[]{4,6,7,12,7,7,9,8,7,5,13,5,6,8,2,13,4,4,1,9,5,13,2,2,12,8,10,8,5,2}), new int[]{8, 7}));
//        System.out.println(java.util.Arrays.equals(solution(29, 20, new int[]{13,10,8,8,5,10,11,13,10,9,8,5,11,11,4,9,3,9,13,3,5,12,4,13,3,4,5,4,11}), new int[]{4, 3}));
//    }


    //比赛匹配问题
//    public static int solution(int n) {
//        // write code here
//        if(n==1){
//            return 0;
//        }
//        int count = 0;
//        while (n / 2 != 0) {
//            if (n % 2 == 0) {
//                count += (n / 2);
//                n /= 2;
//            } else {
//                count += ((n - 1) / 2);
//                n = ((n - 1) / 2 + 1);
//            }
//        }
//        return count;
//
//    }
//
//    public static void main(String[] args) {
//        System.out.println(solution(7) == 6);
//        System.out.println(solution(14) == 13);
//        System.out.println(solution(1) == 0);
//    }


    //二进制之和
//        public static String solution(String binary1, String binary2) {
//            // Please write your code here
//            int sum1 = 0;
//            int sum2=0;
//            for (int i = 0; i < binary1.length(); i++) {
//                int a = binary1.charAt(i) - '0';
//                sum1=sum1*2+a;
//            }
//            for (int i = 0; i < binary2.length(); i++) {
//                int a = binary2.charAt(i) - '0';
//                sum2=sum2*2+a;
//            }
//
//            StringBuilder sb = new StringBuilder();
//            sb.append(sum1+sum2);
//            return sb.toString();
//        }
//
//        public static void main(String[] args) {
//            // You can add more test cases here
//            System.out.println(solution("101", "110").equals("11"));
//            System.out.println(solution("111111", "10100").equals("83"));
//            System.out.println(solution("111010101001001011", "100010101001").equals("242420"));
//            System.out.println(solution("111010101001011", "10010101001").equals("31220"));
//        }
}

